home *** CD-ROM | disk | FTP | other *** search
/ 3D GFX / 3D GFX.iso / amiutils / i_l / irit5 / cagd_lib / cbzreval.c < prev    next >
C/C++ Source or Header  |  1995-12-30  |  17KB  |  391 lines
  1. /******************************************************************************
  2. * CBzrEval.c - Bezier curves handling routines - evaluation routines.          *
  3. *******************************************************************************
  4. * Written by Gershon Elber, Mar. 90.                          *
  5. ******************************************************************************/
  6.  
  7. #include <ctype.h>
  8. #include <stdio.h>
  9. #include <string.h>
  10. #include "cagd_loc.h"
  11.  
  12. static int PowerCacheFineNess,
  13.     BezierCacheEnabled = FALSE,
  14.     CacheFineNess = 0;
  15. static CagdRType *BezierCache[CAGD_MAX_BEZIER_CACHE_ORDER + 1]
  16.                  [CAGD_MAX_BEZIER_CACHE_ORDER + 1];
  17.  
  18. static int IChooseK[CAGD_MAX_BEZIER_CACHE_ORDER + 1]
  19.            [CAGD_MAX_BEZIER_CACHE_ORDER + 1] =
  20. {
  21.     {    1,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0  },
  22.     {    1,    1,    0,    0,    0,    0,    0,    0,    0,    0,    0  },
  23.     {    1,    2,    1,    0,    0,    0,    0,    0,    0,    0,    0  },
  24.     {    1,    3,    3,    1,    0,    0,    0,    0,    0,    0,    0  },
  25.     {    1,    4,    6,    4,    1,    0,    0,    0,    0,    0,    0  },
  26.     {    1,    5,   10,   10,    5,    1,    0,    0,    0,    0,    0  },
  27.     {    1,    6,   15,   20,   15,    6,    1,    0,    0,    0,    0  },
  28.     {    1,    7,   21,   35,   35,   21,    7,    1,    0,    0,    0  },
  29.     {    1,    8,   28,   56,   70,   56,   28,    8,    1,    0,    0  },
  30.     {    1,    9,   36,   84,  126,  126,   84,   36,    9,    1,    0  },
  31.     {    1,   10,   45,  120,  210,  252,  210,  120,   45,   10,    1  }
  32. };
  33.  
  34. static CagdRType BzrCrvEvalFuncAux(int i, int k, CagdRType t);
  35. static CagdRType IntPow(CagdRType x, int i);
  36.  
  37. /*****************************************************************************
  38. * DESCRIPTION:                                                               M
  39. * Sets the bezier sampling cache - if enabled, a Bezier can be evaluated     M
  40. * directly from presampled basis function.                     M
  41. *                                                                            *
  42. * PARAMETERS:                                                                M
  43. *   FineNess:       Number of samples to support (power of 2).               M
  44. *   EnableCache:    Are we really planning on using this thing?              M
  45. *                                                                            *
  46. * RETURN VALUE:                                                              M
  47. *   void                                                                     M
  48. *                                                                            *
  49. * KEYWORDS:                                                                  M
  50. *   BzrCrvSetCache, evaluation, caching                                      M
  51. *****************************************************************************/
  52. void BzrCrvSetCache(int FineNess, CagdBType EnableCache)
  53. {
  54.     int i, j, k;
  55.  
  56.     if (BezierCacheEnabled == EnableCache && FineNess == CacheFineNess)
  57.     return;
  58.  
  59.     if (BezierCacheEnabled) {
  60.     /* Free old cache if was one. */
  61.     for (k = 2; k <= CAGD_MAX_BEZIER_CACHE_ORDER; k++)
  62.         for (i = 0; i < k; i++)
  63.         if (BezierCache[k][i] != NULL) {
  64.             IritFree((VoidPtr) BezierCache[k][i]);
  65.             BezierCache[k][i] = NULL;
  66.         }
  67.     }
  68.  
  69.     if ((BezierCacheEnabled = EnableCache) != FALSE) {
  70.     /* Allocate the new cache and initalize it: */
  71.     if (FineNess < 2)
  72.         FineNess = 2;
  73.     if (FineNess > CAGD_MAX_BEZIER_CACHE_FINENESS)
  74.         FineNess = CAGD_MAX_BEZIER_CACHE_FINENESS;
  75.     CacheFineNess = FineNess;
  76.     PowerCacheFineNess = 1 << FineNess;
  77.  
  78.     for (k = 2; k <= CAGD_MAX_BEZIER_CACHE_ORDER; k++)/* For all orders. */
  79.         for (i = 0; i < k; i++) {      /* Allocate and set all basis func. */
  80.         BezierCache[k][i] = (CagdRType *)
  81.             IritMalloc(sizeof(CagdRType) * PowerCacheFineNess);
  82.         for (j = 0; j < PowerCacheFineNess; j++)
  83.             BezierCache[k][i][j] = BzrCrvEvalFuncAux(i, k,
  84.                 ((CagdRType) j) / (PowerCacheFineNess - 1));
  85.         }
  86.     }
  87. }
  88.  
  89. /*****************************************************************************
  90. * DESCRIPTION:                                                               M
  91. * Assumes Vec holds control points for scalar bezier curve of order Order,   M
  92. * and evaluates and returns that curve value at parameter value t.         M
  93. *   Vec is incremented by VecInc (usually by 1) after each iteration.         M
  94. *                                                                            *
  95. * PARAMETERS:                                                                M
  96. *   Vec:            Coefficents of a scalar Bspline univariate function.     M
  97. *   VecInc:         Step to move along Vec.                                  M
  98. *   Order:          Order of associated geometry.                            M
  99. *   t:              Parameter value where to evaluate the curve.             M
  100. *                                                                            *
  101. * RETURN VALUE:                                                              M
  102. *   CagdRType:      Geometry's value at parameter value t.                   M
  103. *                                                                            *
  104. * KEYWORDS:                                                                  M
  105. *   BzrCrvEvalVecAtParam, evaluation                                         M
  106. *****************************************************************************/
  107. CagdRType BzrCrvEvalVecAtParam(CagdRType *Vec,
  108.                    int VecInc,
  109.                    int Order,
  110.                    CagdRType t)
  111. {
  112.     int i;
  113.     CagdRType
  114.     R = 0.0;
  115.  
  116.     if (VecInc == 1)
  117.     for (i = 0; i < Order; i++)
  118.         R += BzrCrvEvalFuncAux(i, Order, t) * *Vec++;
  119.     else
  120.     for (i = 0; i < Order; i++) {
  121.         R += BzrCrvEvalFuncAux(i, Order, t) * *Vec;
  122.         Vec += VecInc;
  123.     }
  124.  
  125.     return R;
  126. }
  127. /*****************************************************************************
  128. * DESCRIPTION:                                                               M
  129. * Returns a pointer to a static data, holding the value of the curve at      M
  130. * given parametric location t. The curve is assumed to be Bezier.         M
  131. *                                                                            *
  132. * PARAMETERS:                                                                M
  133. *   Crv:      To evaluate at the given parametric location t.                M
  134. *   t:        The parameter value at which the curve Crv is to be evaluated. M
  135. *                                                                            *
  136. * RETURN VALUE:                                                              M
  137. *   CagdRType *:  A vector holding all the coefficients of all components    M
  138. *                 of curve Crv's point type. If for example the curve's      M
  139. *                 point type is P2, the W, X, and Y will be saved in the     M
  140. *                 first three locations of the returned vector. The first    M
  141. *                 location (index 0) of the returned vector is reserved for  M
  142. *                 the rational coefficient W and XYZ always starts at second M
  143. *                 location of the returned vector (index 1).                 M
  144. *                                                                            *
  145. * KEYWORDS:                                                                  M
  146. *   BzrCrvEvalAtParam, evaluation                                            M
  147. *****************************************************************************/
  148. CagdRType *BzrCrvEvalAtParam(CagdCrvStruct *Crv, CagdRType t)
  149. {
  150.     static CagdRType Pt[CAGD_MAX_PT_COORD];
  151.     CagdBType
  152.     IsNotRational = !CAGD_IS_RATIONAL_CRV(Crv);
  153.     int i, j,
  154.     k = Crv -> Order,
  155.     MaxCoord = CAGD_NUM_OF_PT_COORD(Crv -> PType);
  156.     CagdRType B;
  157.  
  158.     for (j = IsNotRational; j <= MaxCoord; j++)
  159.     Pt[j] = 0.0;
  160.  
  161.     for (i = 0; i < k; i++) {
  162.     B = BzrCrvEvalFuncAux(i, k, t);
  163.     for (j = IsNotRational; j <= MaxCoord; j++)
  164.         Pt[j] += B * Crv -> Points[j][i];
  165.     }
  166.  
  167.     return Pt;
  168. }
  169. /*****************************************************************************
  170. * DESCRIPTION:                                                               M
  171. * Samples the curve at FineNess location equally spaced in the curve's       M
  172. * parametric domain.                                 M
  173. *                                                                            *
  174. * PARAMETERS:                                                                M
  175. *   Crv:         To approximate as a polyline.                               M
  176. *   FineNess:    Control on number of samples.                               M
  177. *   Points:      Where to put the resulting polyline.                        M
  178. *   A:           Optional alpha matrix for refinement.                       M
  179. *                                                                            *
  180. * RETURN VALUE:                                                              M
  181. *   int:         The actual number of samples placed in Points. Always       M
  182. *                less than or eaul to FineNess.                              M
  183. *                                                                            *
  184. * KEYWORDS:                                                                  M
  185. *   BzrCrvEvalToPolyline, conversion, refinement, evaluation                 M
  186. *****************************************************************************/
  187. void BzrCrvEvalToPolyline(CagdCrvStruct *Crv,
  188.               int FineNess,
  189.               CagdRType *Points[])
  190. {
  191.     CagdBType
  192.     UseCache = BezierCacheEnabled &&
  193.            FineNess == PowerCacheFineNess &&
  194.            Crv -> Order <= CAGD_MAX_BEZIER_CACHE_ORDER,
  195.     IsNotRational = !CAGD_IS_RATIONAL_CRV(Crv);
  196.     int i, j, Count,
  197.     k = Crv -> Order,
  198.     MaxCoord = CAGD_NUM_OF_PT_COORD(Crv -> PType);
  199.     CagdRType B;
  200.  
  201.     if (UseCache) {
  202.     for (Count = 0; Count < PowerCacheFineNess; Count++) {
  203.         for (j = IsNotRational; j <= MaxCoord; j++)
  204.         Points[j][Count] = 0.0;
  205.         for (i = 0; i < k; i++) {
  206.         B = BezierCache[k][i][Count];
  207.         for (j = IsNotRational; j <= MaxCoord; j++)
  208.             Points[j][Count] += B * Crv -> Points[j][i];
  209.         }
  210.     }
  211.     }
  212.     else {
  213.     for (Count = 0; Count < FineNess; Count++) {
  214.         for (j = IsNotRational; j <= MaxCoord; j++)
  215.         Points[j][Count] = 0.0;
  216.         for (i = 0; i < k; i++) {
  217.         B = BzrCrvEvalFuncAux(i, k,
  218.                       ((CagdRType) Count) / (FineNess - 1));
  219.         for (j = IsNotRational; j <= MaxCoord; j++)
  220.             Points[j][Count] += Crv -> Points[j][i] * B;
  221.         }
  222.     }
  223.     }
  224. }
  225.  
  226. /*****************************************************************************
  227. * DESCRIPTION:                                                               *
  228. * Evaluates the i'th Bezier basis function of order k, at parametric value t *
  229. * (t in [0..1]).                                 *
  230. *   This function is:           i     k - i - 1          i             *
  231. *            Bi,k(t) = ( ) * t          * (1 - t)             *
  232. *                   k                         *
  233. *                                                                            *
  234. * PARAMETERS:                                                                *
  235. *   i:   I'th basi function.                                                 *
  236. *   k:   Degree of the curve.                                                *
  237. *   t:   Parameter value at which to evaluate the Bezier basis function.     *
  238. *                                                                            *
  239. * RETURN VALUE:                                                              *
  240. *   CagdRType:  Value of the i'th Bezier basis function of degree k at t.    *
  241. *****************************************************************************/
  242. static CagdRType BzrCrvEvalFuncAux(int i, int k, CagdRType t)
  243. {
  244.     if (APX_EQ(t, 0.0))
  245.     return (CagdRType) (i == 0);
  246.     else if (APX_EQ(t, 1.0))
  247.     return (CagdRType) (i == k - 1);
  248.     else
  249.     return (k >= CAGD_MAX_BEZIER_CACHE_ORDER ?
  250.             CagdIChooseK(i, k - 1) : (CagdRType) IChooseK[k - 1][i]) *
  251.            IntPow(1.0 - t, k - i - 1) * IntPow(t, i);
  252. }
  253.  
  254. /*****************************************************************************
  255. * DESCRIPTION:                                                               *
  256. * Computes x to the power of i, i integer.                     *
  257. *                                                                            *
  258. *                                                                            *
  259. * PARAMETERS:                                                                *
  260. *   x, i: Description says it all.                                           *
  261. *                                                                            *
  262. * RETURN VALUE:                                                              *
  263. *   CagdRType:  Integer power of x, computed using pwoer of 2's.             *
  264. *****************************************************************************/
  265. static CagdRType IntPow(CagdRType x, int i)
  266. {
  267.     CagdRType Power, RetVal;
  268.  
  269.     for (Power = x, RetVal = 1.0; i != 0; i >>= 1) {
  270.     if (i & 0x01)
  271.        RetVal *= Power;
  272.     
  273.     Power = SQR(Power);
  274.     }
  275.  
  276.     return RetVal;
  277. }
  278.  
  279. /*****************************************************************************
  280. * DESCRIPTION:                                                               M
  281. * Evaluates the following (in floating point arithmetic):             M
  282. *             k         k!                         V
  283. *            ( ) = -------------                     V
  284. *             i    i! * (k - i)!                     V
  285. *                                                                            *
  286. * PARAMETERS:                                                                M
  287. *   i, k:   Coefficients of i choose k.                                      M
  288. *                                                                            *
  289. * RETURN VALUE:                                                              M
  290. *   CagdRType:   Result of i choose k, in floating point, to prevent from    M
  291. *                overflows.                                                  M
  292. *                                                                            *
  293. * KEYWORDS:                                                                  M
  294. *   CagdIChooseK, evaluation, combinatorics                                  M
  295. *****************************************************************************/
  296. CagdRType CagdIChooseK(int i, int k)
  297. {
  298.     int j;
  299.     CagdRType
  300.     c = 1.0;
  301.  
  302.     if ((k >> 1) > i) {                /* i is less than half of k: */
  303.     for (j = k - i + 1; j <= k; j++)
  304.         c *= j;
  305.     for (j = 2; j <= i; j++)
  306.         c /= j;
  307.     }
  308.     else {
  309.     for (j = i + 1; j <= k; j++)
  310.         c *= j;
  311.     for (j = 2; j <= k - i; j++)
  312.         c /= j;
  313.     }
  314.  
  315.     return c;
  316. }
  317.  
  318. #ifdef K_CHOOSE_I_GEN
  319.  
  320. /*****************************************************************************
  321. * DESCRIPTION:                                                               *
  322. * Evaluate the following (in integer arithmetic):                 *
  323. *             k         k!                         *
  324. *            ( ) = -------------                     *
  325. *             i    i! * (k - i)!                     *
  326. *                                                                            *
  327. * PARAMETERS:                                                                *
  328. *   i, k:   Coefficients of i choose k.                                      *
  329. *                                                                            *
  330. * RETURN VALUE:                                                              *
  331. *   int: Result of i choose k.                                               *
  332. *****************************************************************************/
  333. static int IChooseKGenOne(int i, int k)
  334. {
  335.     int j;
  336.     long c = 1;
  337.  
  338.     if ((k >> 1) > i) {                /* i is less than half of k: */
  339.     for (j = k - i + 1; j <= k; j++)
  340.         c *= j;
  341.     for (j = 2; j <= i; j++)
  342.         c /= j;
  343.     }
  344.     else {
  345.     for (j = i + 1; j <= k; j++)
  346.         c *= j;
  347.     for (j = 2; j <= k - i; j++)
  348.         c /= j;
  349.     }
  350.  
  351.     return (int) c;
  352. }
  353.  
  354. /*****************************************************************************
  355. * DESCRIPTION:                                                               *
  356. * Evaluates IChooseK for all possiblities and prints them for the         *
  357. * IChooseK table defined in the beginning of this file.                 *
  358. *                                                                            *
  359. * PARAMETERS:                                                                *
  360. *   None                                                                     *
  361. *                                                                            *
  362. * RETURN VALUE:                                                              *
  363. *   void                                                                     *
  364. *****************************************************************************/
  365. void IChooseKGen(void)
  366. {
  367.     int i, j;
  368.  
  369.     for (i = 0; i <= MAX_BEZIER_CACHE_ORDER; i++) {
  370.     printf(" },\n    {");
  371.     for (j = 0; j <= MAX_BEZIER_CACHE_ORDER; j++)
  372.         printf(" %4d,", j <= i ? IChooseKGenOne(j ,i) : 0);
  373.     }
  374. }
  375.  
  376. /*****************************************************************************
  377. * DESCRIPTION:                                                               *
  378. * Main routine to create the table in the beginning of this file.         *
  379. * PARAMETERS:                                                                *
  380. *   None                                                                     *
  381. *                                                                            *
  382. * RETURN VALUE:                                                              *
  383. *   void                                                                     *
  384. *****************************************************************************/
  385. void main(void)
  386. {
  387.     IChooseKGen();
  388. }
  389.  
  390. #endif /* K_CHOOSE_I_GEN */
  391.